# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        q = [(root, [None, None])]
        while q:
            node, min_max = q.pop(0)
            if not node:
                continue
            if node.left:
                if node.left.val >= node.val:
                    return False
                if min_max[0] != None and node.left.val <= min_max[0]:
                    return False
                q.append((node.left, [min_max[0], node.val]))
            if node.right:
                if node.right.val <= node.val:
                    return False
                if min_max[1] != None and node.right.val >= min_max[1]:
                    return False
                q.append((node.right, [node.val, min_max[1]]))
        return True
